package org.design.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * 测试排序
 *
 * @author 樊温军
 * @date 2025/6/23 下午2:44
 */
public class TestSort {

    private static final int DATA_SIZE = 100000;

    @Test
    public void sort() {
        int[] arr = {8, 5, 1, 7, 0, 9};

        long start = 0;
        long end = 0;

        // 测试插入排序
        /*arr = DataUtils.getRandomArray(DATA_SIZE);
        start = System.currentTimeMillis();
        insertionSort(arr);
        end = System.currentTimeMillis();
        System.out.println("插入排序耗时：" + (end - start) + "ms");*/

        // 测试希尔排序
        /*arr = DataUtils.getRandomArray(DATA_SIZE);
        start = System.currentTimeMillis();
        shellSort(arr);
        end = System.currentTimeMillis();
        System.out.println("希尔排序耗时：" + (end - start) + "ms");*/

        // 测试归并排序
        /*arr = DataUtils.getRandomArray(DATA_SIZE);
        start = System.currentTimeMillis();
        mergeSort(arr);
        end = System.currentTimeMillis();
        System.out.println("归并排序耗时：" + (end - start) + "ms");*/

        // 测试快速排序
        /*arr = DataUtils.getRandomArray(DATA_SIZE);
        start = System.currentTimeMillis();
        quickSort(arr);
        end = System.currentTimeMillis();
        System.out.println("快速排序耗时：" + (end - start) + "ms");*/

        arr = DataUtils.getRandomArray(10);
        System.out.println(Arrays.toString(arr));
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & (arr[i] - 1)) == 0) {
//                System.out.println(i + "位2的幂运算：" + arr[i]);
            }
            if (arr[i] % 2 == 0) {
                System.out.println(i + "位偶数：" + arr[i]);
            }
        }
    }

    /**
     * InsertionSort
     * 插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。
     * 插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，
     * 这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，
     * 最坏的情况是 O(n^2)。
     *
     * @param arr 待排序数组
     */
    private void insertionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j > 0 && j < arr.length; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }

            /*StringBuilder sb = new StringBuilder();
            sb.append("第").append(i + 1).append("轮排序：");
            for (int k = 0; k <= i + 1 && k < arr.length; k++) {
                sb.append(arr[k]).append(" ");
            }
            System.out.println(sb);*/

        }
    }


    /**
     * 希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。
     * 希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快
     * ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，
     * 总之比一般 O(n^2 ) 复杂度的算法快得多。
     *
     * @param arr 待排序数组
     */
    private void shellSort(int[] arr) {
        int len = arr.length;
        for (int gap = len / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < len; i++) {
                int temp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = temp;
            }
        }
    }

    /**
     * 归并排序
     * 当有 n 个记录时，需进行 logn 轮归并排序，每一轮归并，其比较次数不超过 n，
     * 元素移动次数都是 n，因此，归并排序的时间复杂度为 O(nlogn)。
     * 归并排序时需要和待排序记录个数相等的存储空间，所以空间复杂度为 O(n)。
     * 归并排序适用于数据量大，并且对稳定性有要求的场景。
     */
    private void mergeSort(int[] arr) {

        int n = arr.length;
        sort(arr, 0, n - 1);
    }

    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private static void merge(int[] arr, int l, int mid, int r) {

        int[] aux = Arrays.copyOfRange(arr, l, r + 1);
        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {
                // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l] < aux[j - l]) {
                // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i - l];
                i++;
            } else {
                // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    // 递归使用归并排序,对arr[l...r]的范围进行排序
    private static void sort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
        // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, l, mid, r);
        }
    }

    /**
     * 快速排序是一种比较快速的排序算法，它的平均运行时间是 O(nlogn)，
     * 之所以特别快是由于非常精练和高度优化的内部循环，最坏的情形性能为 O(n^2)
     * 。像归并一样，快速排序也是一种分治的递归算法。
     * 从空间性能上看，快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归，
     * 空间复杂度也为O(logn)。
     */
    private void quickSort(int[] arr) {
        int n = arr.length;
        quickSort(arr, 0, n - 1);
    }

    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = quickSort2Ways(arr, l, r);
//        int p = partition(arr, l, r);
        quickSort(arr, l, p - 1);
        quickSort(arr, p + 1, r);
    }

    // 对arr[l...r]部分进行partition操作
    // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
    private int partition(int[] arr, int l, int r) {
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);
        int v = arr[l];
        // arr[l+1...j] < v ; arr[j+1...i) > v
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                j++;
                swap(arr, j, i);
            }
        }
        swap(arr, l, j);
        return j;
    }

    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    /**
     * 双路快速排序
     * 时间和空间复杂度同随机化快速排序。
     * 对于有大量重复元素的数组，如果使用上一节随机化快速排序效率是非常低的，
     * 导致 partition 后大于基点或者小于基点数据的子数组长度会极度不平衡，
     * 甚至会退化成 O(n*2) 时间复杂度的算法，对这种情况可以使用双路快速排序算法。
     */
    private int quickSort2Ways(int[] arr, int l, int r) {
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);
        int v = arr[l];
        // arr[l+1...i) <= v; arr(j...r] >= v
        int i = l + 1, j = r;
        while (true) {
            while (i <= r && arr[i] < v) {
                i++;
            }
            while (j >= l + 1 && arr[j] > v) {
                j--;
            }
            if (i > j) {
                break;
            }
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

}
